#include "graph.h"
#include "uni_set.h"
using namespace std;

Graph::Graph(int V)
{
    //初始化点数
    this->V=V;
    //新建邻接链表保存各边
    this->adjList=new list<Edge>*[V];
    for(int i=0;i<V;i++)
    {
        adjList[i]=new list<Edge>;
    }
    edges=new list<Edge>;
}

Graph::~Graph()
{
    delete edges;
    for(int i=0;i<V;i++)
        delete adjList[i];
    delete []adjList;
}
void
Graph::addEdge(int start,int end,int weight)
{
    this->adjList[start]->push_back(Edge(start,end,weight));
    this->edges->push_back(Edge(start,end,weight));
    this->adjList[end]->push_back(Edge(end,start,weight));
}

void
Graph::printMap()
{
    for(int i=0;i<V;i++)
    {
        list<Edge>::iterator iter;
        for(iter=adjList[i]->begin();iter!=adjList[i]->end();iter++)
        {
            cout<<*iter<<"\t";
        }
        cout<<endl;
    }
}

list<Edge> *
Graph::kruskal()
{
    list<Edge> * res=new list<Edge>;    //新建边集A
    UnionSet * uniSet=new UnionSet(V);  //初始化并查集
    edges->sort();  //排序边集合
    list<Edge>::iterator iter;  //新建迭代器
    for(iter=edges->begin();iter!=edges->end();iter++)  //遍历每一条边
    {
        if(!uniSet->same(iter->start,iter->end)) //如果u和v不属于同一棵树
        {
            res->push_back(*iter);//添加边进A
            uniSet->unite(iter->start,iter->end);//合并u和v
        }
    }
    return res; //返回结果
}

list<Edge> *
Graph::prim()
{
    list<Edge> * res=new list<Edge>;  //结果的链表
    PrimStruct * ps=new PrimStruct[V];  //新建一个结构体数组
    bool * inQ=new bool[V]; //标示一个点是否在队列中
    priority_queue<PrimStruct> Q;//优先队列
    for(int i=0;i<V;i++)    //初始化结构体数组
    {
        ps[i].id=i;
        ps[i].key=INF;
        ps[i].pi=NIL;
    }
    ps[0].key=0;   //将0设为根
    for(int i=0;i<V;i++)    //依次推入各点的值
    {
        Q.push(ps[i]);
        inQ[i]=true;    //表示某点在队列中
    }
    while(!Q.empty())   //当队列不为空时执行
    {
        int u=Q.top().id;   //取出队列中key最小的点
        Q.pop();    //抛出
        inQ[u]=false;   //标识点不在队列中
        list<Edge>::iterator iter;
        for(iter=adjList[u]->begin();iter!=adjList[u]->end();iter++)    //遍历u所有的邻接点v与(u,v)边长
        {
            if(inQ[iter->end]&&iter->length<ps[iter->end].key)    //如果v在队列中，并且有更小的边
            {
                ps[iter->end].pi=u; //设置前驱
                ps[iter->end].key=iter->length;   //设置轻边的长度
            }
        }
    }
    
    for(int i=1;i<V;i++)	//整理结果链表
    {
        res->push_back(Edge(ps[i].pi,i,ps[i].key));//加入结果
    }
    delete[] inQ;
    delete[] ps;
    return res;
}
